package listnode;

import listnode.data.ListNode;

import java.util.*;


/**
 * 链表中的下一个更大节点 （2024 拼多多）
 *
 * 先反转，再用栈 或者单调队列
 */
public class NextLargerNodes {

    public int[] nextLargerNodes(ListNode head) {

        if (head==null){
            return null;
        }

        Stack<Integer> reverseStack=new Stack<>();
        ListNode cur=head;
        int len=0;
        while (cur!=null){
            reverseStack.push(cur.val);
            cur=cur.next;
            len++;
        }

        int ret[]=new int[len];
//        Deque<Integer> queue=new ArrayDeque<>();
//        while (!reverseStack.isEmpty()){
//            int value=reverseStack.pop();
//            while (!queue.isEmpty()&&value>=queue.peekFirst()){
//                queue.pollFirst();
//            }
//            ret[--len]=queue.isEmpty()?0:queue.peekFirst();
//            queue.offerFirst(value);
//        }


        Stack<Integer> queue=new Stack<>();
        while (!reverseStack.isEmpty()){
            int value=reverseStack.pop();
            while (!queue.isEmpty()&&value>=queue.peek()){
                queue.pop();
            }
            ret[--len]=queue.isEmpty()?0:queue.peek();
            queue.push(value);
        }

        return ret;
    }



    public static void main(String[] args) {
        int[] values = {1,7,5,1,9,2,5,1};
        ListNode head = createLinkedList(values);
        printLinkedList(head);

        int r[]=new NextLargerNodes().nextLargerNodes(head);
        System.out.println(r.toString());
    }

    public static ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int value : values) {
            current.next = new ListNode(value);
            current = current.next;
        }
        return dummy.next;
    }

    public static void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }


}
